|
In combinatorics, a square-free word is a word (a sequence of characters) that does not contain any subword twice in a row. Thus a square-free word is one that avoids the pattern ''XX''.〔Lothaire (2011) p.112〕〔Lothaire (2011) p.114〕 ==Examples== Over a two-letter alphabet the only square-free words are the empty word and ''a'', ''b'', ''ab'', ''ba'', ''aba'', and ''bab''. However, there exist infinite square-free words in any alphabet with three or more symbols,〔 as proved by Axel Thue.〔A. Thue, Über unendliche Zeichenreihen, Norske Vid. Skrifter I Mat.-Nat. Kl., Christiania 7 (1906) 1–22.〕〔A. Thue, Über die gegenseitige Lage gleicher Teile gewisser Zeichenreihen, Norske Vid. Skrifter I Mat.-Nat. Kl., Christiania 1 (1912) 1–67.〕 One example of an infinite square-free word over an alphabet of size 3 is the word over the alphabet obtained by taking the first difference of the Thue–Morse sequence.〔Pytheas Fogg (2002) p.104〕〔Berstel et al (2009) p.97〕 That is, from the Thue–Morse sequence :0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, ... one forms a new sequence in which each term is the difference of two consecutive terms of the Thue–Morse sequence. The resulting square-free word is :1, 0, −1, 1, −1, 0, 1, 0, −1, 0, 1, −1, 1, 0, −1, ... . Another example found by John Leech is defined recursively over the alphabet . Let be any word starting with the letter ''a''. Define the words recursively as follows: the word is obtained from by replacing each ''a'' in with , each ''b'' with , and each ''c'' with . It is possible to check that the sequence converges to the infinite square-free word : 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「squarefree word」の詳細全文を読む スポンサード リンク
|